// 不同的二叉搜索树

package Leetcode;

class solution_096 {
    public int numTrees(int n) {
        // dp[i]表示用i个数能构造的二叉搜索树的数量
        int[] dp = new int[n + 1];
        // 初始化
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n + 1; i++) {
            // 分别以j为头结点
            for (int j = 1; j <= i; j++) {
                int left = j - 1;
                int right = i - j;
                dp[i] += dp[left] * dp[right];
            }
        }
        return dp[n];
    }
}

public class Solution096 {

}
